//42
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 1) {
            return 0;
        }
        int len = height.length;
        int[] dpl = new int[len];
        int[] dpr = new int[len];
        dpl[0] = height[0];
        dpr[len-1] = height[len-1];
        for (int i = 1; i < len; i++) {
            dpl[i] = Math.max(dpl[i-1], height[i]);
        }
        for (int i = len-2; i >= 0; i--) {
            dpr[i] = Math.max(dpr[i+1], height[i]);
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            dpl[i] = (Math.min(dpl[i], dpr[i]) - height[i]);
            sum += dpl[i];
        }
        return sum;
    }
}
//面试题17.19
class Solution {
    public int[] missingTwo(int[] nums) {
        int len = nums.length;
        int sum = 0;
        int[] ret = new int[2];

        for (int i = 0; i < len; i++) {
            sum ^= nums[i];
            sum ^= i+1;
        }
        sum ^= len+1;
        sum ^= len+2;
        sum = ((~sum)+1) & sum;
        for (int i = 0; i < len; i++) {
            if ((nums[i] ^ sum) > nums[i]) {
                ret[0] ^= nums[i];
            }
            else {
                ret[1] ^= nums[i];
            }
            if ((sum ^ (i+1)) > (i+1)) {
                ret[0] ^= (i+1);
            }
            else {
                ret[1] ^= (i+1);
            }
        }
        if ((sum ^ (len+1)) > (len+1)) {
            ret[0] ^= (len+1);
        }
        else {
            ret[1] ^= (len+1);
        }
        if ((sum ^ (len+2)) > (len+2)) {
            ret[0] ^= (len+2);
        }
        else {
            ret[1] ^= (len+2);
        }
        return ret;
    }
}
//1576
class Solution {
    public String modifyString(String s) {
        char[] arr =  s.toCharArray();
        int len = arr.length;
        if (len == 1) {
            return arr[0] == '?' ? "a" : s;
        }
        for (int i = 0; i < len; i++) {
            if (arr[i] == '?') {
                char tmp = 'a';
                while (tmp == arr[i != len-1 ? i+1 : i] || 
                    tmp == arr[i != 0 ? i-1 : 0]) {
                    tmp++;
                }
                arr[i] = tmp;
            }
        }
        return new String(arr);
    }
}